1. Technical Field
The present invention relates generally to delivering messages in communication or multiprocessor networks (generally referred to as networks). More particularly, the present invention relates to an adaptive and dynamic message routing system for delivering messages in wormhole networks using multiple level routing tables at each node of the network.
2. Description of the Background art
Communication networks that are generally used to interconnect computers or those used in telecommunication often comprise a number of nodes and communication links (links, routes) as shown in FIG. 1. Each node generally comprises a processor, one or more storage units and several I/O ports for connecting that node to the other nodes in the network. For example, in FIG. 1, node N1 may communicate to node N2 over communication link N1-N2 and node N3 may communicate to node N5 over communication link N3-N5. Each node in the network is generally capable of acting as a source, sink, and an intermediate node. Source node is a node where the message to be communicated is generated and transmitted from; sink destination) node is a node where the message generated by the source is to be communicated to (delivered to); and an intermediate node is a node between a source and a destination node encountered by the message in its route to the destination node. Furthermore, each message sent over the network generally comprises a message header and the information to be transmitted. The message header generally includes the address of the destination node where the message is supposed to be delivered and the address of the source node where the message was generated from.
As mentioned above, the network is generally utilized to deliver electronic messages among various nodes in the network. Furthermore, a majority of multinode communication networks have been arranged as either a "connection type" network, a "connectionless type" network or as a "wormhole" network.
In a connection type network, all of the data transfer takes place via a communication path which is completely established from a source node to a destination node by a message header before the message is transferred. In this type of network, the communication path established between the source node and destination node, including all the intermediate nodes and links, is held up and not released until the message has been completely delivered.
In a connectionless type network ("store and forward" network), a message is transferred from a source node to a destination node via packets (packets or datagrams refer to a message to be transmitted) where the packets are stored at each intermediate node until a connection is made to the next node (either intermediate or destination node) at which time the data is then transferred to that next node. Connectionless type networks require large buffer (memory) space at each node for storing and forwarding messages from one node to the next node in the network.
In wormhole networks, a message is transmitted from a source node to a destination node immediately after the message header has been transmitted thus avoiding storing and forwarding of the message at each intermediate node. By not storing and forwarding the message at each node, wormhole routing avoids using large memory buffers, and the delays associated with using these memory buffers, at each node of the network. This results in tremendous memory savings in the network as a whole.
Traditionally, wormhole routing techniques have relied on the network topology to route messages and to avoid deadlocks and bottlenecks. For example, E-cube routing routes messages in the order of dimensions in a hypercube network. Address-delta routing techniques route messages in X and then Y directions based on the difference between the address of the source and destination in a mesh network. Unfortunately, these routing techniques rely directly on the network topology and therefore, are not transferable from one network topology to another or vice versa. Also, in the past network topologies have imposed limits on the exact number of nodes in a network. For example, hypercube networks limit the number of nodes in the network to a power of 2 and a mesh network cannot support any prime number of nodes. Furthermore, as the number of nodes and links in a network increases, efficient message delivery and avoiding bottlenecks and preventing messages from endless travelling becomes an ever growing concern.
Therefore, there is a dire need for a message delivery and routing method and apparatus that is independent of a network topology (i.e., an adaptive method and apparatus); wherein the routing decisions are distributed among the nodes of the network (i.e., dynamic routing); and which at the same time can deliver messages in the shortest possible time using the minimum amount of network resources.